/*-------------------------------------------------------------------------
 *
 * ginpostinglist.c
 *	  处理帖子列表的例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/gin/ginpostinglist.c
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/gin_private.h"

#ifdef USE_ASSERT_CHECKING
#define CHECK_ENCODING_ROUNDTRIP
#endif

/*
 * 为了编码目的，项指针被表示为64位无符号整数。最低11位表示偏移量编号，接下来的32位是块编号。这留下了21位未使用，即只有43位低位被使用。
 *
 * 11位足以表示偏移量编号，因为在所有支持的块大小中，MaxHeapTuplesPerPage < 2^11。我们对比特位使用非常节省，因为较小的整数在varbyte编码中使用较少的字节，从而节省磁盘空间。（如果将来我们得到一个新的表AM，想要使用可能的偏移量编号的完整范围，我们需要对此进行更改。）
 *
 * 这些43位整数是使用varbyte编码的。在每个字节中，7个低位包含数据，而最高位是一个连续位。当连续位被设置时，下一个字节是同一个整数的一部分，否则这是该整数的最后一个字节。在这种编码中，43位最多需要7个字节：
 *
 * 0XXXXXXX
 * 1XXXXXXX 0XXXXYYY
 * 1XXXXXXX 1XXXXYYY 0YYYYYYY
 * 1XXXXXXX 1XXXXYYY 1YYYYYYY 0YYYYYYY
 * 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 0YYYYYYY
 * 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 0YYYYYYY
 * 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 0uuuuuuY
 *
 * X = 用于偏移量编号的位
 * Y = 用于块编号的位
 * u = 未使用的位
 *
 * 字节以小端顺序存储。
 *
 * 这种编码的一个重要属性是，从列表中移除一个项目从不会增加结果压缩发布列表的大小。证明：
 *
 * 移除编号实际上是用它们的和替换两个数字。我们必须证明，一个和的varbyte编码不会比其加数的varbyte编码长。两个数字的和最多比较大的加数多一个比特。将一个数字宽度扩大一个比特最多会使其在varbyte编码中的长度增加一个字节。因此，和的varbyte编码最多比较大加数的varbyte编码长一个字节。较小的加数至少占用一个字节，因此和不能占用比加数更多的空间，Q.E.D.
 *
 * 这个属性大大简化了VACUUM，它可以假设发布列表在清理后总是适合同一页面。请注意，尽管在从发布列表中删除项目时这成立，但在与压缩列表合并未压缩项时，您必须小心不要导致扩展，例如在清理时。
 */

/*
 * 编码偏移量编号需要多少位？OffsetNumber是一个16位整数，但您不能在一个页面上放下那么多项。11位应该足够了。从MaxHeapTuplesPerPage推导出这一点并使用最小的比特数是很有诱惑力的，但如果MaxHeapTuplesPerPage发生变化，这将需要更改磁盘格式。最好留些余地。
 */
#define MaxHeapTuplesPerPageBits		11

/* 编码最大支持整数所需的最大字节数。 */
#define MaxBytesPerInteger				7

static inline uint64 fc_itemptr_to_uint64(const ItemPointer fc_iptr)
{
	uint64		fc_val;

	Assert(ItemPointerIsValid(fc_iptr));
	Assert(GinItemPointerGetOffsetNumber(fc_iptr) < (1 << MaxHeapTuplesPerPageBits));

	fc_val = GinItemPointerGetBlockNumber(fc_iptr);
	fc_val <<= MaxHeapTuplesPerPageBits;
	fc_val |= GinItemPointerGetOffsetNumber(fc_iptr);

	return fc_val;
}

static inline void fc_uint64_to_itemptr(uint64 fc_val, ItemPointer fc_iptr)
{
	GinItemPointerSetOffsetNumber(fc_iptr, fc_val & ((1 << MaxHeapTuplesPerPageBits) - 1));
	fc_val = fc_val >> MaxHeapTuplesPerPageBits;
	GinItemPointerSetBlockNumber(fc_iptr, fc_val);

	Assert(ItemPointerIsValid(fc_iptr));
}

/*
 * Varbyte-编码 'val' 到 *ptr。*ptr 被递增到下一个整数。
 */
static void fc_encode_varbyte(uint64 fc_val, unsigned char **fc_ptr)
{
	unsigned char *fc_p = *fc_ptr;

	while (fc_val > 0x7F)
	{
		*(fc_p++) = 0x80 | (fc_val & 0x7F);
		fc_val >>= 7;
	}
	*(fc_p++) = (unsigned char) fc_val;

	*fc_ptr = fc_p;
}

/*
 * 解码在 *ptr 处的 varbyte-编码整数。*ptr 被递增到下一个整数。
 */
static uint64 fc_decode_varbyte(unsigned char **fc_ptr)
{
	uint64		fc_val;
	unsigned char *fc_p = *fc_ptr;
	uint64		fc_c;

	/* 第1字节 */
	fc_c = *(fc_p++);
	fc_val = fc_c & 0x7F;
	if (fc_c & 0x80)
	{
		/* 第2字节 */
		fc_c = *(fc_p++);
		fc_val |= (fc_c & 0x7F) << 7;
		if (fc_c & 0x80)
		{
			/* 第3字节 */
			fc_c = *(fc_p++);
			fc_val |= (fc_c & 0x7F) << 14;
			if (fc_c & 0x80)
			{
				/* 第4字节 */
				fc_c = *(fc_p++);
				fc_val |= (fc_c & 0x7F) << 21;
				if (fc_c & 0x80)
				{
					/* 第5字节 */
					fc_c = *(fc_p++);
					fc_val |= (fc_c & 0x7F) << 28;
					if (fc_c & 0x80)
					{
						/* 第6字节 */
						fc_c = *(fc_p++);
						fc_val |= (fc_c & 0x7F) << 35;
						if (fc_c & 0x80)
						{
							/* 第7字节，应没有续位 */
							fc_c = *(fc_p++);
							fc_val |= fc_c << 42;
							Assert((fc_c & 0x80) == 0);
						}
					}
				}
			}
		}
	}

	*fc_ptr = fc_p;

	return fc_val;
}

/*
 * 编码一个Posting列表。
 *
 * 编码后的列表在一个palloc的结构中返回，大小最多为 'maxsize' 字节。返回的段中的项数
 * 在 *nwritten 中返回。如果不等于 nipd，则并非所有项都适合在 'maxsize' 中，只有前 *nwritten 被编码。
 *
 * 返回结构的分配大小是短对齐的，如果有，末尾的填充字节为零。
 */
GinPostingList *
ginCompressPostingList(const ItemPointer fc_ipd, int fc_nipd, int fc_maxsize,
					   int *fc_nwritten)
{
	uint64		fc_prev;
	int			fc_totalpacked = 0;
	int			fc_maxbytes;
	GinPostingList *fc_result;
	unsigned char *fc_ptr;
	unsigned char *fc_endptr;

	fc_maxsize = SHORTALIGN_DOWN(fc_maxsize);

	fc_result = palloc(fc_maxsize);

	fc_maxbytes = fc_maxsize - offsetof(GinPostingList, bytes);
	Assert(fc_maxbytes > 0);

	/* 存储第一个特殊项 */
	fc_result->first = fc_ipd[0];

	fc_prev = fc_itemptr_to_uint64(&fc_result->first);

	fc_ptr = fc_result->bytes;
	fc_endptr = fc_result->bytes + fc_maxbytes;
	for (fc_totalpacked = 1; fc_totalpacked < fc_nipd; fc_totalpacked++)
	{
		uint64		fc_val = fc_itemptr_to_uint64(&fc_ipd[fc_totalpacked]);
		uint64		fc_delta = fc_val - fc_prev;

		Assert(fc_val > fc_prev);

		if (fc_endptr - fc_ptr >= MaxBytesPerInteger)
			fc_encode_varbyte(fc_delta, &fc_ptr);
		else
		{
			/*
			 * 剩余少于7个字节。在写出之前必须检查下一个
			 * 项是否适合该空间。
			 */
			unsigned char fc_buf[MaxBytesPerInteger];
			unsigned char *fc_p = fc_buf;

			fc_encode_varbyte(fc_delta, &fc_p);
			if (fc_p - fc_buf > (fc_endptr - fc_ptr))
				break;			/* 输出已满 */

			memcpy(fc_ptr, fc_buf, fc_p - fc_buf);
			fc_ptr += (fc_p - fc_buf);
		}
		fc_prev = fc_val;
	}
	fc_result->nbytes = fc_ptr - fc_result->bytes;

	/*
	 * 如果我们写了奇数个字节，将末尾的填充字节归零。
	 */
	if (fc_result->nbytes != SHORTALIGN(fc_result->nbytes))
		fc_result->bytes[fc_result->nbytes] = 0;

	if (fc_nwritten)
		*fc_nwritten = fc_totalpacked;

	Assert(SizeOfGinPostingList(fc_result) <= fc_maxsize);

	/*
	 * 检查编码段是否解码回原始项。
	 */
#if defined (CHECK_ENCODING_ROUNDTRIP)
	{
		int			fc_ndecoded;
		ItemPointer fc_tmp = ginPostingListDecode(fc_result, &fc_ndecoded);

		Assert(fc_ndecoded == fc_totalpacked);
		Assert(memcmp(fc_tmp, fc_ipd, fc_ndecoded * sizeof(ItemPointerData)) == 0);
		pfree(fc_tmp);
	}
#endif

	return fc_result;
}

/*
 * 将压缩的Posting列表解码成一组项指针数组。
 * 项的数量在 *ndecoded 中返回。
 */
ItemPointer ginPostingListDecode(GinPostingList *fc_plist, int *fc_ndecoded)
{
	return ginPostingListDecodeAllSegments(fc_plist,
										   SizeOfGinPostingList(fc_plist),
										   fc_ndecoded);
}

/*
 * 将多个Posting列表段解码成一组项指针数组。
 * 项的数量在 *ndecoded_out 中返回。这些段一个接一个存储，
 * 总大小为 'len' 字节。
 */
ItemPointer ginPostingListDecodeAllSegments(GinPostingList *fc_segment, int fc_len, int *fc_ndecoded_out)
{
	ItemPointer fc_result;
	int			fc_nallocated;
	uint64		fc_val;
	char	   *fc_endseg = ((char *) fc_segment) + fc_len;
	int			fc_ndecoded;
	unsigned char *fc_ptr;
	unsigned char *fc_endptr;

	/*
	 * 猜测数组的初始大小。
	 */
	fc_nallocated = fc_segment->nbytes * 2 + 1;
	fc_result = palloc(fc_nallocated * sizeof(ItemPointerData));

	fc_ndecoded = 0;
	while ((char *) fc_segment < fc_endseg)
	{
		/* 如有需要，扩大输出数组 */
		if (fc_ndecoded >= fc_nallocated)
		{
			fc_nallocated *= 2;
			fc_result = repalloc(fc_result, fc_nallocated * sizeof(ItemPointerData));
		}

		/* 复制第一个项 */
		Assert(OffsetNumberIsValid(ItemPointerGetOffsetNumber(&fc_segment->first)));
		Assert(fc_ndecoded == 0 || ginCompareItemPointers(&fc_segment->first, &fc_result[fc_ndecoded - 1]) > 0);
		fc_result[fc_ndecoded] = fc_segment->first;
		fc_ndecoded++;

		fc_val = fc_itemptr_to_uint64(&fc_segment->first);
		fc_ptr = fc_segment->bytes;
		fc_endptr = fc_segment->bytes + fc_segment->nbytes;
		while (fc_ptr < fc_endptr)
		{
			/* 如有需要，扩大输出数组 */
			if (fc_ndecoded >= fc_nallocated)
			{
				fc_nallocated *= 2;
				fc_result = repalloc(fc_result, fc_nallocated * sizeof(ItemPointerData));
			}

			fc_val += fc_decode_varbyte(&fc_ptr);

			fc_uint64_to_itemptr(fc_val, &fc_result[fc_ndecoded]);
			fc_ndecoded++;
		}
		fc_segment = GinNextPostingListSegment(fc_segment);
	}

	if (fc_ndecoded_out)
		*fc_ndecoded_out = fc_ndecoded;
	return fc_result;
}

/*
 * 将一堆Posting列表中的所有项指针添加到TIDBitmap中。
 */
int ginPostingListDecodeAllSegmentsToTbm(GinPostingList *fc_ptr, int fc_len,
									 TIDBitmap *fc_tbm)
{
	int			fc_ndecoded;
	ItemPointer fc_items;

	fc_items = ginPostingListDecodeAllSegments(fc_ptr, fc_len, &fc_ndecoded);
	tbm_add_tuples(fc_tbm, fc_items, fc_ndecoded, false);
	pfree(fc_items);

	return fc_ndecoded;
}

/*
 * 合并两个有序的项指针数组，消除任何重复项。
 *
 * 返回一个palloc的数组，*nmerged 被设置为结果中的项数，
 * 在消除重复项之后。
 */
ItemPointer ginMergeItemPointers(ItemPointerData *fc_a, uint32 fc_na,
					 ItemPointerData *fc_b, uint32 fc_nb,
					 int *fc_nmerged)
{
	ItemPointerData *fc_dst;

	fc_dst = (ItemPointer) palloc((fc_na + fc_nb) * sizeof(ItemPointerData));

	/*
	 * 如果参数数组不重叠，我们可以直接将它们追加到一起。
	 */
	if (fc_na == 0 || fc_nb == 0 || ginCompareItemPointers(&fc_a[fc_na - 1], &fc_b[0]) < 0)
	{
		memcpy(fc_dst, fc_a, fc_na * sizeof(ItemPointerData));
		memcpy(&fc_dst[fc_na], fc_b, fc_nb * sizeof(ItemPointerData));
		*fc_nmerged = fc_na + fc_nb;
	}
	else if (ginCompareItemPointers(&fc_b[fc_nb - 1], &fc_a[0]) < 0)
	{
		memcpy(fc_dst, fc_b, fc_nb * sizeof(ItemPointerData));
		memcpy(&fc_dst[fc_nb], fc_a, fc_na * sizeof(ItemPointerData));
		*fc_nmerged = fc_na + fc_nb;
	}
	else
	{
		ItemPointerData *fc_dptr = fc_dst;
		ItemPointerData *fc_aptr = fc_a;
		ItemPointerData *fc_bptr = fc_b;

		while (fc_aptr - fc_a < fc_na && fc_bptr - fc_b < fc_nb)
		{
			int			fc_cmp = ginCompareItemPointers(fc_aptr, fc_bptr);

			if (fc_cmp > 0)
				*fc_dptr++ = *fc_bptr++;
			else if (fc_cmp == 0)
			{
				/* 仅保留一份相同项的副本 */
				*fc_dptr++ = *fc_bptr++;
				fc_aptr++;
			}
			else
				*fc_dptr++ = *fc_aptr++;
		}

		while (fc_aptr - fc_a < fc_na)
			*fc_dptr++ = *fc_aptr++;

		while (fc_bptr - fc_b < fc_nb)
			*fc_dptr++ = *fc_bptr++;

		*fc_nmerged = fc_dptr - fc_dst;
	}

	return fc_dst;
}
